package 剑指Offer1;

public class _11连续子数组的最大和 {
    //dp(i):是以nums[i]结尾的最大连续子序列和
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = dp[0] = nums[0]; //以nums[0]结尾的最大值，初始状态
        for(int i=1;i<nums.length;++i){
            if(dp[i-1]<=0){
                dp[i] = nums[i];
            }else {
                dp[i] = dp[i-1] + nums[i];
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    public int maxSubArray2(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int dp = nums[0];
        int max = dp;
        for(int i=1;i<nums.length;++i){
            if(dp<=0){
                dp = nums[i];
            }else {
                dp = dp + nums[i];
            }
            max = Math.max(max,dp);
        }
        return max;
    }
}
